from decimal import Decimal
from math import ceil
from typing import List


# 数学、高精度、动态规划


MAX_INT = 10 ** 7 + 1


class Solution:
    def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:
        size = len(dist)

        # 计算每段路需要的用时
        time = [Decimal(d) / Decimal(speed) for d in dist]
        # print("每段路的最短用时:", time)

        # dp[i][j] = 完成第i条道路，跳过j次休息时间的最短时间
        dp = [[MAX_INT] * size for _ in range(size + 1)]
        dp[0][0] = 0

        # 处理不跳过休息时间的情况
        for i in range(1, size + 1):
            dp[i][0] = ceil(dp[i - 1][0]) + time[i - 1]

        # 状态转移
        for i in range(2, size + 1):
            for j in range(1, i):
                dp[i][j] = min(ceil(dp[i - 1][j]) + time[i - 1], dp[i - 1][j - 1] + time[i - 1])

        # for row in dp:
        #     print(row)

        # print(dp[-1][-1])

        # 计算结果
        for j in range(size):
            if dp[-1][j] <= hoursBefore + pow(10, -9):
                return j

        return -1


if __name__ == "__main__":
    print(Solution().minSkips(dist=[1, 3, 2], speed=4, hoursBefore=2))  # 1
    print(Solution().minSkips(dist=[7, 3, 5, 5], speed=2, hoursBefore=10))  # 2
    print(Solution().minSkips(dist=[7, 3, 5, 5], speed=1, hoursBefore=10))  # -1

    # 测试用例54/56
    print(Solution().minSkips(dist=[1, 1, 1, 1, 1], speed=10000000, hoursBefore=1))  # 4

    # 自制用例
    print(Solution().minSkips(dist=[10000] * 1000, speed=10000000, hoursBefore=1))  # 999
    print(Solution().minSkips(dist=[10001] * 1000, speed=10000000, hoursBefore=1))  # -1
    print(Solution().minSkips(dist=[10001] * 999 + [9001], speed=10000000, hoursBefore=1))  # 999
    print(Solution().minSkips(dist=[100000] * 1000, speed=1, hoursBefore=10000000))  # -1
    print(Solution().minSkips(dist=[100000] * 1000, speed=10, hoursBefore=10000000))  # 0

    # 自制用例
    print(Solution().minSkips(dist=[5], speed=4, hoursBefore=1))  # -1
    print(Solution().minSkips(dist=[5], speed=5, hoursBefore=1))  # 0
    print(Solution().minSkips(dist=[1], speed=50000, hoursBefore=1))  # 0
    print(Solution().minSkips(dist=[1, 2, 4], speed=7, hoursBefore=1))  # 2

    # 测试用例55/56
